package org.basis.algorithm.sort.practice;

import org.basis.algorithm.common.SortUtil;
import org.basis.algorithm.tree.common.TreeNode;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 基础排序算法练习
 *
 * @author Mr_wenpan@163.com 2022/02/24 21:11
 */
public class BaseSort01 {

    public static String clear(String str) {
        if (str == null || str.length() < 1) {
            return str;
        }

        // 双指针
        char[] chars = str.toCharArray();
        int l = 0;
        int r = chars.length - 1;
        // 先除去括号，然后再去除 < 左边的值得到最终结果
        while (l < r) {
            char lchar = str.charAt(l);
            char rchar = str.charAt(r);
            if (lchar != '(') {
                l++;
            }
            if (rchar != ')') {
                r--;
            }
            if (lchar == '(' && rchar == ')') {
                break;
            }
        }

        // 有括号存在，去除括号
        String newStr = str;
        if (l < r) {
            String s1 = str.substring(0, l);
            String s2 = str.substring(r + 1, str.length());
            newStr = s1 + s2;
        }

        // 去除<左边的字符
        int index = newStr.lastIndexOf("<");
        newStr = newStr.substring(index + 1, newStr.length());

        return newStr;
    }

    public static void main(String[] args) {


        final String str = "abcdef<<gh(sfdsjfsf>slfjs>>><<<)xyz";
        String clear = clear(str);
        System.out.println(clear);
//        bubbleSortTest();
//        selectionSortTest();
//        insertionSortTest();
    }

    /**
     * 迭代的方式遍历二叉树
     *
     * @param root       根节点
     * @param resultList 遍历结果
     * @author Mr_wenpan@163.com 2022/2/24 11:25 下午
     */
    public void process2(TreeNode<Integer> root, List<Integer> resultList) {

        if (root == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack = new Stack<>();
        stack.push(root);
        TreeNode<Integer> cur = root.left;
        while (!stack.isEmpty() || cur != null) {
            if (cur == null) {
                TreeNode<Integer> pop = stack.pop();
                resultList.add(pop.data);
                cur = pop.right;
            } else {
                stack.push(cur);
                cur = cur.left;
            }
        }

    }

    public static void bubbleSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            bubbleSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("bad way.");
            }
        }
    }

    public static void selectionSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            selectionSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("sorry the result is error.");
            }
        }
    }

    public static void insertionSortTest() {
        for (int i = 0; i < 10000; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            insertionSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("bad result.");
            }
        }
    }

    /**
     * 插入排序
     */
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 对于每一个位置都会往前比较，找到合适的插入位置
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     */
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            // 记录每一轮的最小位置
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            // 结算
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
